def patition_left(A,p,q): #q超出末端位置
    x=A[p]
    i=p
    for j in range(p+1,q): #q=p+1时 range空
        if A[j]<=x:
            i=i+1
            A[i],A[j]=A[j],A[i]
    A[p],A[i]=A[i],A[p]
    return i
def patition(A,p,r):
    x=A[r-1]
    i=p-1
    for j in range(p,r-1):
        if A[j]<=x:
            i=i+1
            A[i],A[j]=A[j],A[i]
    A[r-1],A[i+1]=A[i+1],A[r-1]
    return i+1
def do_quick_sort(A,p,r):
    if p<r:
        q=patition(A,p,r)
        do_quick_sort(A,p,q)
        do_quick_sort(A,q+1,r)
    return A

def quick_sort(A):
    n=len(A)
    return do_quick_sort(A,0,n)

if __name__=='__main__':
    A=[11,5,2,6,77,23,8,4,123]
    print A
    print quick_sort(A)
    
    
